package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

public class _04_06_inorder_successor {
    
    /**
     * 我感觉吧，这个题，还是两个解法
     *
     * 芜湖蒙对了
     * */
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        this.p = p;
        return suc(root);
    }
    TreeNode prev;
    TreeNode p;
    TreeNode suc(TreeNode node) {
        if (node == null) return null;
        TreeNode left = suc(node.left);
        if (left != null) return left;
        if (prev != null && prev == p)
            return node;
        prev = node;
        return suc(node.right);
    }
    
    /**
     * 这道题应该用中序遍历的定义来找
     *
     * 只是普通二分查找，我感觉好难
     *
     * */
    public TreeNode inorderSuccessor2(TreeNode root, TreeNode p) {
        if (p.right != null) {
            p = p.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        TreeNode res = null;
        while (root != null) {
            if (root.val > p.val) {
                res = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return res;
    }
}
